Link to this headingMulti Party Computation Signatures

Link to this headingMPC ECDSA

Using [Shamir’s Secret Sharing](/Crypto/Key Derivation/Shamir’s Secret Sharing.md) to split a key you can use ECDSA on the shares to make partial signatures to join into the full signature.

Link to this headingImplementation

import secrets from hashlib import sha256 from ecdsa import SigningKey, SECP256k1, util from functools import reduce def modinv(a, n): """Modular inverse using Extended Euclidean Algorithm""" return pow(a, -1, n) def lagrange_interpolate(x, x_s, y_s, q): """Lagrange interpolation at x over finite field""" total = 0 k = len(x_s) for i in range(k): xi, yi = x_s[i], y_s[i] li = 1 for j in range(k): if i != j: xj = x_s[j] li *= (x - xj) * modinv(xi - xj, q) li %= q total += yi * li total %= q return total def shamir_share(secret, threshold, num_shares, q): """Generate Shamir shares of the secret""" coeffs = [secret] + [(secrets.randbelow(q-1) + 1) for _ in range(threshold - 1)] shares = [] for i in range(1, num_shares + 1): x = i y = sum([coeffs[j] * pow(x, j, q) for j in range(threshold)]) % q shares.append((x, y)) return shares def signature_verify(r, s, z, pub_key, q): from ecdsa.ecdsa import Public_key, Signature pub = Public_key(G, pub_key) sig = Signature(r, s) valid = pub.verifies(z, sig) print(f"Signature valid: {valid}") print(f"Signature: r = {r}, s = {s}") return valid if __name__ == "__main__": # Initialize curve and generator curve = SECP256k1 G = curve.generator order = curve.order # Secret key priv_key = secrets.randbelow(order-1) +1 # Ensure it's in the range [1, order-1] pub_key = priv_key * G # Parameters for threshold scheme threshold = 3 # threshold num_shares = 5 # total parties # Create shares shares = shamir_share(priv_key, threshold, num_shares, order) print(f"Generated shares: {shares}") # Message to sign message = b"Threshold ECDSA PoC" message_hash = int.from_bytes(sha256(message).digest(), 'big') % order # Generate a random k that is the same for all parties k = secrets.randbelow(order-1) + 1 # Ensure k is in the range [1, order-1] R = k * G r = R.x() % order k_inv = modinv(k, order) selected_shares = shares[:threshold] x_s = [x for (x, _) in selected_shares] # Each party computes its share of s # s_i = (message_hash + random_point * share_y) % order partial_signatures = [] for x_i, y_i in selected_shares: s_i = (message_hash + r * y_i) % order partial_signatures.append((x_i, s_i)) # Combine shares using Lagrange interpolation to get full s # s = k_inv * L(0, x_s, [s_i for (_, s_i) in partial_signatures]) % order compbined_s = sum((s_i * lagrange_interpolate(0, x_s, [s for (_, s) in partial_signatures], order)) for (_, s_i) in partial_signatures) % order s = (k_inv * lagrange_interpolate(0, x_s, [s for (_, s) in partial_signatures], order)) % order # ---------- Verification ---------- valid = signature_verify(r, s, message_hash, pub_key, order) print(f"Signature verification result: {valid}") # Generated shares: [(1, mpz(3384796937180342578786757632028104081747638960432769905687896486996564190165)), (2, mpz(29174177386549707398991491821137283830538312579713319210734786325067765297975)), (3, mpz(83655921441766214215161280143676828999475799876656045425820216496384855267201)), (4, mpz(51037939865513667603725137590958831735722536572186044168339023859429672603506)), (5, mpz(47112321895108262988254049171671199892116086945378219820896371555720378801227))] # Signature valid: True # Signature: r = 80062998148642071209212203377843622668975090302755313217799995105627231040726, s = 2577493232225470942764247866215246781870590692477676719505009113885254605295 # Signature verification result: True

Link to this headingToy Example

#Setup Keys and message order = 13 generator = 2 private_key = 5 #Share Function:f(x) = 5 + ax mod 13 #x = 1 share1 = (1,6) # f(1) = 6 share2 = (2,7) # f(2) = 7 hashed_message = 2 #Setup secret Number for signature secret_int = 3 inverse_secret_int = pow(secret_int, -1, order) public_int = (secret_int * generator) % order print(f"Public Int: {public_int}, Inverse Secret Int: {inverse_secret_int}, Private Key: {private_key}") #Signature Parts signature_1 = (hashed_message + public_int * share1[1]) % order signature_2 = (hashed_message + public_int * share2[1]) % order print(f"Signature 1: {signature_1}, Signature 2: {signature_2}") #Lagrange weights lambda_1 = ((0 - share2[0])//(share1[0] - share2[0])) % order lambda_2 = ((0 - share1[0])//(share2[0] - share1[0])) % order print(f"Lagrange Weights: lambda_1 = {lambda_1}, lambda_2 = {lambda_2}") #Identities #lambda_1 + lambda_2 = 1 # This is because we are using Lagrange interpolation at x=0, which gives us # the constant term of the polynomial, which is the sum of the weights. #lambda_1 * share1[1] + lambda_2 * share2[1] = private_key # hashed_message + public_int * private_key = lambda_1 * signature_1 + lambda_2 * signature_2 # ... = lambda_1 * ((hashed_message + public_int * share1[1]) % order) + lambda_2 * ((hashed_message + public_int * share2[1]) % order) # ... = (lambda_1 * hashed_message) + (lambda_1 * public_int * share1[1]) + (lambda_2 * hashed_message) + (lambda_2 * public_int * share2[1]) # ... = hashed_message(lambda_1 + lambda_2 ) + public_int(lambda_1 * share1[1] + lambda_2 * share2[1]) # ... = hashed_message + public_int(lambda_1 * share1[1] + lambda_2 * share2[1]) # ... = hashed_message + public_int * private_key signature_whole = (lambda_1 * signature_1 + lambda_2 * signature_2) % order # s = k^-1 * (hashed_message + public_int * private_key) combined_signature = (inverse_secret_int * signature_whole) % order print(f"Combined Signature: {combined_signature}") #Signature signature = (public_int, combined_signature) print(f"Signature: {signature}") # Public Int: 6, Inverse Secret Int: 9, Private Key: 5 # Signature 1: 12, Signature 2: 5 # Lagrange Weights: lambda_1 = 2, lambda_2 = 12 # Combined Signature: 2 # Signature: (6, 2)

Link to this headingSecurity

partial_signature_1 = hashed_message + public_int * share1[1]

share1[1] = (partial_signature_1 - hashed_message) / public_int

Example Attack:


import secrets
from hashlib import sha256
from ecdsa import SECP256k1
from ecdsa.ecdsa import Public_key, Signature
from functools import reduce

def modinv(a, n):
    """Modular inverse using Extended Euclidean Algorithm"""
    return pow(a, -1, n)

def lagrange_interpolate(x, x_s, y_s, q):
    """Lagrange interpolation at x over finite field"""
    total = 0
    k = len(x_s)
    for i in range(k):
        xi, yi = x_s[i], y_s[i]
        li = 1
        for j in range(k):
            if i != j:
                xj = x_s[j]
                li *= (x - xj) * modinv(xi - xj, q)
                li %= q
        total += yi * li
        total %= q
    return total

def shamir_share(secret, threshold, num_shares, q):
    """Generate Shamir shares of the secret"""
    coeffs = [secret] + [(secrets.randbelow(q-1) + 1) for _ in range(threshold - 1)]
    shares = []
    for i in range(1, num_shares + 1):
        x = i
        y = sum([coeffs[j] * pow(x, j, q) for j in range(threshold)]) % q
        shares.append((x, y))
    return shares

def signature_verify(r, s, z, pub_key, q):
    pub = Public_key(G, pub_key)
    sig = Signature(r, s)
    return pub.verifies(z, sig)

# Initialize curve and generator
curve = SECP256k1
G = curve.generator
order = curve.order

# Secret key
priv_key = secrets.randbelow(order - 1) + 1
pub_key = priv_key * G
print(f"Private key: {priv_key}")

# Threshold settings
threshold = 3
num_shares = 5
shares = shamir_share(priv_key, threshold, num_shares, order)
print(f"Generated shares: {shares}")

# Sign message
message = b"Threshold ECDSA PoC"
z = int.from_bytes(sha256(message).digest(), 'big') % order

# Generate nonce
k = secrets.randbelow(order - 1) + 1
R = k * G
r = R.x() % order
k_inv = modinv(k, order)

# Select shares for signing
selected_shares = shares[:threshold]
x_s = [x for (x, _) in selected_shares]

# Compute partial signatures
partial_signatures = []
for x_i, y_i in selected_shares:
    s_i = (z + r * y_i) % order
    partial_signatures.append((x_i, s_i))

# Interpolate to get s
s = (k_inv * lagrange_interpolate(0, x_s, [s for (_, s) in partial_signatures], order)) % order
valid = signature_verify(r, s, z, pub_key, order)
print(f"Signature valid: {valid}")

# Leak the second partial signature
leaked_xi1, leaked_si1 = partial_signatures[1]  # attacker gets this
# Use the partial signature to recover the second share
leaked_yi1 = ((leaked_si1 - z) * modinv(r, order)) % order  # recover y_i from s_i

#Leak the third share
leaked_xi2, leaked_si2 = partial_signatures[2]  # attacker gets this
# Use the partial signature to recover the third share
leaked_yi2 = ((leaked_si2 - z) * modinv(r, order)) % order  # recover y_i from s_i

# Now attacker has y1 and y2; simulate getting one more partial signature
recovered_shares = [
    (selected_shares[0][0], selected_shares[0][1]),  # share 1
    (leaked_xi1, leaked_yi1),                          # recovered share 2
    (leaked_xi2, leaked_yi2)   # recovered share 3
]
print(f"Recovered shares: {recovered_shares}")

x_leaked = [x for (x, _) in recovered_shares]
y_leaked = [y for (_, y) in recovered_shares]

# Interpolate secret
recovered_key = lagrange_interpolate(0, x_leaked, y_leaked, order)
print(f"Recovered private key: {recovered_key}")

assert recovered_key == priv_key, "Recovered key does not match original private key!"


Link to this headingGG18


Link to this headingGG20


Link to this headingCGGMP21